class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();
        for (int first = 0; first < n - 3; first++){
            if (first > 0 && nums[first] == nums[first -1]) continue;
            for (int second = first + 1; second < n - 2; second++){
                if (second > first + 1 && nums[second] == nums[second - 1]) continue;
                int third = second + 1, fourth = n - 1;
                long long mark = (long long)target - nums[first] - nums[second];
                while (third < fourth){
                    if ((long long)nums[third] + nums[fourth] < mark) third++;
                    else if ((long long)nums[third] + nums[fourth] > mark) fourth--;
                    else if ((long long)nums[third] + nums[fourth] == mark){
                        vv.push_back({nums[first], nums[second], nums[third], nums[fourth]});
                        while (third < n - 1 && nums[third] == nums[third + 1]) third++;
                        while (fourth > third && nums[fourth] == nums[fourth - 1]) fourth--;
                        third++; fourth--;
                    }

                }
            }
        }
        return vv;
        

    }
};
